//中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。 
//
// 
// 例如 arr = [2,3,4] 的中位数是 3 。 
// 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。 
// 
//
// 实现 MedianFinder 类: 
//
// 
// MedianFinder() 初始化 MedianFinder 对象。 
// void addNum(int num) 将数据流中的整数 num 添加到数据结构中。 
// double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10⁻⁵ 以内的答案将被接受。 
// 
//
// 示例 1： 
//
// 
//输入
//["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
//[[], [1], [2], [], [3], []]
//输出
//[null, null, null, 1.5, null, 2.0]
//
//解释
//MedianFinder medianFinder = new MedianFinder();
//medianFinder.addNum(1);    // arr = [1]
//medianFinder.addNum(2);    // arr = [1, 2]
//medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
//medianFinder.addNum(3);    // arr[1, 2, 3]
//medianFinder.findMedian(); // return 2.0 
//
// 提示: 
//
// 
// -10⁵ <= num <= 10⁵ 
// 在调用 findMedian 之前，数据结构中至少有一个元素 
// 最多 5 * 10⁴ 次调用 addNum 和 findMedian 
// 
//
// Related Topics 设计 双指针 数据流 排序 堆（优先队列） 👍 1146 👎 0


import java.util.PriorityQueue;

//leetcode submit region begin(Prohibit modification and deletion)
class MedianFinder {
    //保证小顶堆（右边）的元素始终大于等于大顶堆（左边）的元素
    PriorityQueue<Integer> maxHeap ;//大顶堆的所有元素总是小于等于小顶堆的元素（栈顶）
    PriorityQueue<Integer> minHeap ;

    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a,b)->b-a);//大顶堆，
        minHeap = new PriorityQueue<>();//小顶堆
    }
    
    public void addNum(int num) {
        //约定：两个堆元素相同时，把经过比较的元素加到左边（大顶堆）
        if(maxHeap.size() == minHeap.size()) {//两堆元素个数最小时
            minHeap.offer(num);//{加入数字，同时内部的minHeap结构会做一次比较栈顶是《右边》最小元素} 先把数据放到小顶堆中，此时数据经过比较后，栈顶是小顶堆的最小的数字
            maxHeap.offer(minHeap.poll());//再把小顶堆中最小的数据放到大顶堆，维持小顶堆栈顶（最小数字）大于等于大顶堆栈顶（最大数字）
            //即右边的小顶堆栈顶始终存最小数字，左边的大顶堆始终存最大数字
        }
        //约定：两个堆元素相同<左边元素个数比右边大1>时，把经过比较的元素加到右边（小顶堆）
        else{
            maxHeap.offer(num);//{加入数字，同时内部的maxHeap结构会做一次比较栈顶是《左边》最大元素}
            minHeap.offer(maxHeap.poll());
        }
    }
    
    public double findMedian() {
        if(maxHeap.size() == minHeap.size()){
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }else{
            return maxHeap.peek();
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
//leetcode submit region end(Prohibit modification and deletion)
